package everydayone.rob;

/**
 * @Date 2020/05/29
 * @author 王光浩
 * @Thinking 使用 DP
 * 	 int[] help 数组 ——以 i 结尾的能获取的最大金额
 * 	 状态转移方程：
 * 		help[i] = Math.max( help[i-1], help[i-2]+nums[i] )
 * @Analysis 时间复杂度O（n），空间复杂度O（1）
 */
public class MyMethodOne {
	public int rob(int[] nums) {
		if (nums == null || nums.length == 0)
			return 0;
		if (nums.length == 1)
			return nums[0];
		int[] help = new int[nums.length];
		help[0] = nums[0];
		help[1] = Math.max(nums[0], nums[1]);
		for (int i = 2; i < nums.length; i++) {
			help[i] = Math.max(help[i - 1], help[i - 2] + nums[i]);
		}
		return nums[nums.length - 1];
	}
}
